/*
https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/
*/
class Solution {
public:
    vector<int> findLeftSmaller(vector<int>& nums) {
        vector<int> result(nums.size(), 0);
        stack<int> st;
        for (int i = 0; i < nums.size(); ++i) {
            while (!st.empty() && nums[i] <= nums[st.top()]) {
                result[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        return result;
    }
    vector<int> finalPrices(vector<int>& nums) {
        vector<int>res=findLeftSmaller(nums);
        for(int i=0;i<nums.size();++i){
            nums[i]-=res[i];
        }
        return nums;
    }
};